#pragma once

#include <list>
#include <vector>
#include <queue>
#include <map>
#include <iostream>

#define GRAPH_MATRIX
#ifdef GRAPH_MATRIX
template<class V, class W, bool Direction = false>
class Graph
{
private:
    std::vector<V> _vs;
    std::map<V, size_t> _indexMap;
    std::vector<std::vector<W>> _matrix;
public:
    Graph() = default;
    Graph(const std::vector<V>& vs)
    :_vs(vs)
    {
        for(size_t i = 0; i < vs.size(); i++)
        {
            _indexMap[vs[i]] = i;
        }
        _matrix.resize(vs.size());
        for(auto& e : _matrix)
        {
            e.resize(vs.size(), INT32_MAX);
        }
    }

    void AddEdge(const V& st, const V& ed, const W& w = INT32_MAX);
    void Print() const;
};

template<class V, class W, bool Direction>
void Graph<V, W, Direction>::AddEdge(const V& st, const V& ed, const W& w)
{
    size_t sti = _indexMap[st];
    size_t edi = _indexMap[ed];
    _matrix[sti][edi] = w;
}
template<class V, class W, bool Direction>
void Graph<V, W, Direction>::Print() const
{
    for(auto& e : _matrix)
    {
        for(auto& ee : e)
        {
            if(ee == INT32_MAX) std::cout << "*" << " ";
            else std::cout << ee << " ";
        }
        std::cout << std::endl;
    }
}
#else
template <class V, class W>
struct EdgeNode
{
    EdgeNode(V ev, W w = W())
        : _ev(ev), _w(w)
    {}
    V _ev;
    W _w;
};

template <class V, class W, bool Direction = false>
class Graph
{
private:
    std::map<V, std::list<EdgeNode<V, W>>> _g;

public:
    Graph() {}

    void AddEdge(const V& st, const V& ed, const W& w = W());
    void Print() const;
private:
    void _DFS(V v, std::map<V, bool> &query_map);
public:
    // 深度优先遍历
    void DFS(V st);
    // 深度优先生成树
    void DFSTree(V st);
    // 广度优先遍历
    void BFS(V st);
    // 广度优先生成树
    void BFSTree(V st);

    //最小生成树
    //1. Kruskal算法
    void Kruskal();
    //2. Prim算法
    void Prim();
};

template <class V, class W, bool Direction>
void Graph<V, W, Direction>::AddEdge(const V& st, const V& ed, const W& w)
{
    auto it = _g.find(st);
    if (it != _g.end())
    {
        it->second.push_back(EdgeNode<V, W>(ed, w));
    }
    else
    {
        std::list<EdgeNode<V, W>> tmp;
        tmp.push_back(EdgeNode<V, W>(ed, w));
        _g.insert({st, tmp});
    }
}
template <class V, class W, bool Direction>
void Graph<V, W, Direction>::Print() const
{
    std::cout << "邻接表如下" << std::endl;
    for (auto &e : _g)
    {
        std::cout << "顶点:" << e.first;
        for (auto &x : e.second)
        {
            std::cout << "->" << x._ev;
        }
        std::cout << endl;
    }
}
template <class V, class W, bool Direction>
void Graph<V, W, Direction>::_DFS(V v, std::map<V, bool> &query_map)
{
    if (query_map[v] == false)
        return;
    std::cout << "->" << v;
    query_map[v] = false;
    for (auto &e : _g[v])
    {
        if (query_map[e._ev])
        {
            _DFS(e._ev, query_map);
        }
    }
}
template <class V, class W, bool Direction>
void Graph<V, W, Direction>::DFS(V st)
{
    std::map<V, bool> query_map;
    for (auto &e : _g)
    {
        query_map[e.first] = true;
    }
    // 1. 找起点
    query_map[st] = false;
    auto it = _g.find(st);
    if (it == _g.end())
    {
        std::cout << "不存在该定点" << std::endl;
        return;
    }
    // 2. 开始遍历
    std::cout << "DFS:" << st;
    for (auto &e : it->second)
    {
        if (query_map[e._ev])
        {
            _DFS(e._ev, query_map);
        }
    }
    std::cout << endl;
}

template <class V, class W, bool Direction>
void Graph<V, W, Direction>::DFSTree(V st)
{
    std::map<V, bool> query_map;
    for (auto &e : _g)
    {
        query_map[e.first] = true;
    }
    // 1. 找起点
    query_map[st] = false;
    auto it = _g.find(st);
    if (it == _g.end())
    {
        std::cout << "不存在该定点" << std::endl;
        return;
    }
    // 2. 开始遍历
    std::cout << "DFSTree:" << st;
    for (auto &e : it->second)
    {
        if (query_map[e._ev])
        {
            _DFS(e._ev, query_map);
        }
    }
    std::cout << endl;
}

template <class V, class W, bool Direction>
void Graph<V, W, Direction>::BFSTree(V st)
{
    std::queue<V> q;
    std::map<V, bool> query_map;
    for (auto &e : _g)
    {
        query_map[e.first] = true;
    }
    // 1. 找起点
    q.push(st);
    query_map[st] = false;
    auto it = _g.find(st);
    if (it == _g.end())
    {
        std::cout << "不存在该定点" << std::endl;
        return;
    }
    // 2. 开始遍历
    std::cout << "BFSTree:";
    bool flag = true;
    while (!q.empty())
    {
        auto tmp = q.front();
        if (flag)
            std::cout << tmp, flag = false;
        else
            std::cout << "->" << tmp;
        q.pop();
        for (auto &e : _g[tmp])
        {
            if (query_map[e._ev])
            {
                q.push(e._ev);
                query_map[e._ev] = false;
            }
        }
    }
    std::cout << endl;
}

template <class V, class W, bool Direction>
void Graph<V, W, Direction>::BFS(V st)
{
    std::queue<V> q;
    std::map<V, bool> query_map;
    for (auto &e : _g)
    {
        query_map[e.first] = true;
    }
    // 1. 找起点
    q.push(st);
    query_map[st] = false;
    auto it = _g.find(st);
    if (it == _g.end())
    {
        std::cout << "不存在该定点" << std::endl;
        return;
    }
    // 2. 开始遍历
    std::cout << "BFS:";
    bool flag = true;
    while (!q.empty())
    {
        auto tmp = q.front();
        if (flag)
            std::cout << tmp, flag = false;
        else
            std::cout << "->" << tmp;
        q.pop();
        for (auto &e : _g[tmp])
        {
            if (query_map[e._ev])
            {
                q.push(e._ev);
                query_map[e._ev] = false;
            }
        }
    }
    std::cout << endl;
}

#endif